␈↓␈↓ βYSYLLABUS FOR PH.D. QUALIFYING EXAMINATION
␈↓␈↓ β
IN THE MATHEMATICAL ASPECTS OF COMPUTER SCIENCE

␈↓␈↓ ε∩April 1974

␈↓The␈α∂examination␈α∞will␈α∂be␈α∂held␈α∞on␈α∂May␈α∂25.␈α∞ If␈α∂there␈α∂are␈α∞few␈α∂enough␈α∂students␈α∞it␈α∂wil␈α∂be␈α∞oral.
␈↓Otherwise␈αit␈αwill␈αbe␈αfour␈αhours,␈αopen␈αbook␈αstarting␈αat␈α10␈αa.m.


␈↓1.␈α Mathematical␈αLogic␈α([1]␈αor␈α[2],␈αsee␈αthe␈αbibliography␈αin␈α[3.1]

␈↓␈↓ α81.1␈α The␈αPropositional␈αCalculus

␈↓␈↓ α81.2␈α The␈αPredicate␈αCalculus

␈↓␈↓ α81.3␈α Theorem␈αProving␈αby␈αComputers

␈↓2.␈α Theory␈αof␈αComputability␈α([4]␈αor␈α[5])

␈↓␈↓ α82.1␈α Church's␈αThesis␈αand␈αthe␈αequivalence␈αof␈αseveral␈αdefinitions␈αof␈αcomputability,␈αsuch
␈↓␈↓ βλas␈αTuring␈αcomputable,␈αMrkov␈αcomputable␈αand␈αgeneral␈αrecursive.

␈↓␈↓ α82.2␈α↔ Primitive␈α↔recursive␈α↔and␈α↔partial␈α↔recursive␈α↔functions.␈α↔ Ackermann's␈α⊗function.
␈↓␈↓ βλRecursive␈αand␈αrecursively␈αenumerable␈αsets.

␈↓␈↓ α82.3␈α⊗ The␈α⊗Halting␈α⊗problem␈α⊗of␈α⊗Turing␈α⊗machines␈α⊗(and␈α⊗the␈α⊗equivalent␈α↔problem␈α⊗for
␈↓␈↓ βλrecursive␈αfunctions).

␈↓3.␈α Automata␈αTheory␈αand␈αComputational␈αComplexity␈α(p[6]-[8])

␈↓␈↓ α83.1␈α~ Finite␈α≠Automata␈α~(deteministic␈α≠and␈α~non-deterministic),␈α≠regular␈α~expressions
␈↓␈↓ βλ(Kleene␈αTheorem),␈αright-linear␈αlanguages␈αand␈αfinite␈αsemi-groups.

␈↓␈↓ α83.2␈α∪ Push-down␈α∀automata␈α∪(deterministic␈α∀and␈α∪non-deterministic)␈α∀and␈α∪Context-free
␈↓␈↓ βλlanguages.␈α Linear␈αbounded␈αautomata␈αand␈αcontext␈αsensitive␈αlanguages.

␈↓␈↓ α83.3␈α Axiomatic␈αcomputational␈αcomplexity␈αtheory.

␈↓4.␈α Mathematical␈αTheory␈αof␈αComputation

␈↓␈↓ α84.1␈α∞ Methods␈α
for␈α∞proving␈α
properties␈α∞of:␈α
 Compilers,␈α∞program␈α
schemas,␈α∞and␈α
programs.
␈↓␈↓ βλ([9]-[16])

␈↓␈↓ α84.2␈α Semantics␈αof␈αProgramming␈αLanguages.␈α([17]-[18])

␈↓␈↓ α84.3␈α Monotonic␈αand␈αContinuous␈αFunctions.␈α([21]-[22])
␈↓5.␈α Theory␈αof␈αComputation␈αComplexity

␈↓␈↓ α85.1␈α Abstract␈αcomlexity␈αtheory

␈↓␈↓ α85.2␈α P=?NP

␈↓6.␈αMathematical␈αBackground

␈↓␈↓ α86.1␈α Algebra

␈↓␈↓ α86.2␈α Set␈αTheory
␈↓␈↓ ¬rREFERENCES



␈↓[1]␈α Mendelson,␈αE.,␈αINTRODUCTION␈αTO␈αMATHEMATICAL␈αLOGIC.␈α Van␈αNostrand␈α(1964).

␈↓[2]␈α Robbin␈αJ.␈αW.,␈αMATHEMATICAL␈αLOGIC:␈α A␈αFIRST␈αCOURSE.␈αW.␈αA.␈αBenjamin␈α(1969).

␈↓[3]␈α_ Robinson,␈α_J.A.␈α_"A␈α_Review␈α_of␈α_Automatic␈α_Theorem-Proving",␈α_in␈α_MATHEMATICAL
␈↓␈↓ α8ASPECTS␈αOF␈αCOMPUTER␈αSCIENCE.␈α American␈αMathematical␈αSociety␈α(1967).

␈↓[4]␈α Davis,␈αM.,␈αCOMPUTABILITY␈αAND␈αUNSOLVABILITY.␈α McGraw-Hill␈α(1958).

␈↓[5]␈α∃ Hermes,␈α∃H.,␈α∀ENUMERABILITY,␈α∃DECIDABILITY␈α∃AND␈α∃COMPUTABILITY.␈α∀ Academic
␈↓␈↓ α8Press␈α(1965).

␈↓[6]␈α⊗ Minsky,␈α⊗M.,␈α⊗COMPUTATION:␈α⊗ FINITE␈α⊗AND␈α⊗INFINITE␈α⊗MACHINES.␈α∃ Prentice-Hall
␈↓␈↓ α8(1967).

␈↓[7]␈α∪ Rabin,␈α∪M.␈α∪O.␈α∪and␈α∪Scott,␈α∩D.,␈α∪"Finite␈α∪Automata␈α∪and␈α∪Their␈α∪Decision␈α∪Problems".␈α∩ IBM
␈↓␈↓ α8JOURNAL␈α∃3,␈α∃114␈α∀(1959).␈α∃ Also␈α∃in␈α∃SEQUENTIAL␈α∀MACHINES␈α∃(ed.␈α∃E.␈α∃F.␈α∀Moore),
␈↓␈↓ α8Addison-Wesley␈α(1969).

␈↓[8]␈α⊗ Hopcroft,␈α⊗J.␈α↔and␈α⊗Ullman␈α⊗J.,␈α⊗FORMAL␈α↔LANGUAGES␈α⊗AND␈α⊗THEIR␈α↔RELATION␈α⊗TO
␈↓␈↓ α8AUTOMATA.␈α Addison-Wesley␈α(1969).

␈↓[9]␈α McCarthy,␈αJ.,␈αand␈αPainter,␈αJ.,␈α"Correctness␈αof␈αa␈αCompiler␈αfor␈αArithmetic␈αExpressions".␈αin
␈↓␈↓ α8PROCEEDINGS␈αOF␈αSYMPOSIA␈αIN␈αAPPLIED␈αMATHEMATICS,␈αVol.␈α19␈α(1967).

␈↓[10]␈α
Rutledge,␈α
J.␈αD.,␈α
"On␈α
Ianov␈αProgram␈α
Schemata."␈α
JOURNAL␈αOF␈α
THE␈α
ACM,␈αVol.␈α
11,␈α
No.␈α1
␈↓␈↓ α8(1964),␈αpp.␈α1-9.

␈↓[11]␈α∂Luckham,␈α⊂D.␈α∂C.,␈α∂Park,␈α⊂D.␈α∂M.␈α∂R.␈α⊂and␈α∂Paterson,␈α∂M.␈α⊂S.,␈α∂ON␈α⊂FORMALISED␈α∂COMPUTER
␈↓␈↓ α8PROGRAMS.␈α⊂ (Preliminary␈α⊂draft)␈α∂Programming␈α⊂Research␈α⊂Group,␈α⊂Oxford␈α∂University
␈↓␈↓ α8(August␈α1967).

␈↓[12]␈α∩Floyd,␈α∩R.␈α∩W.,␈α∩"Assigning␈α∩Meaning␈α∩to␈α∩Programs".␈α∩in␈α∩MATHEMATICAL␈α∩ASPECTS␈α∩OF
␈↓␈↓ α8COMPUTER␈αSCIENCE.␈α American␈αMathematical␈αSociety␈α(1967).

␈↓[13]␈α⊃McCarthy,␈α⊃J.,␈α⊂"Towards␈α⊃a␈α⊃Mathematical␈α⊂Science␈α⊃of␈α⊃Computation."␈α⊃in␈α⊂PROCEEDINGS
␈↓␈↓ α8IFIP␈αCONGRESS␈α62,␈αNorth-Holland,␈αAmsterdam␈α(1962),␈αpp.␈α21-26.

␈↓[14]␈α∀McCarthy,␈α∪J.,␈α∀"Basis␈α∪for␈α∀a␈α∪Mathematical␈α∀Theory␈α∪of␈α∀Computation."␈α∀in␈α∪COMPUTER
␈↓␈↓ α8PROGRAMMING␈α∞AND␈α∞FORMAL␈α∞SYSTEMS␈α∞(Braffort␈α∞and␈α∞Hirschberg,␈α∞eds.),␈α∞North-
␈↓␈↓ α8Holland␈α(1963),␈αpp.␈α33-70

␈↓[15]␈α
Manna,␈α
Z.,␈α
"Properties␈α
of␈α∞Programs␈α
and␈α
the␈α
First-Order␈α
Predicate␈α
Calculus."␈α∞in␈α
JACM,
␈↓␈↓ α8Vol.␈α16,␈αNo.2␈α(April␈α1969).

␈↓[16]␈α⊃Manna,␈α⊃Z.␈α∩and␈α⊃Pnueli,␈α⊃A.,␈α⊃"Formalization␈α∩of␈α⊃Properties␈α⊃of␈α⊃Functional␈α∩Programs".␈α⊃ in
␈↓␈↓ α8ACM␈αSYMPOSIUM␈αON␈αTHEORY␈αOF␈αCOMPUTING␈α(May␈α1969).
␈↓[17]␈α∂McCarthy,␈α∂J.,␈α∂"A␈α∂Formal␈α∂Description␈α∂of␈α∂a␈α∂Subset␈α∂of␈α∂Algol".␈α∂in␈α⊂FORMAL␈α∂LANGUAGE
␈↓␈↓ α8DESCRIPTION␈α_LANGUAGES␈α↔FOR␈α_COMPUTER␈α↔PROGRAMMING.␈α_ (Steele,␈α↔ed.).
␈↓␈↓ α8North-Holland␈α(1966).

␈↓[18]␈α⊂Lucas,␈α⊂P.,␈α⊂Lauer,␈α∂P.,␈α⊂Stigleitner,␈α⊂H.,␈α⊂METHOD␈α∂AND␈α⊂NOTATION␈α⊂FOR␈α⊂THE␈α∂FORMAL
␈↓␈↓ α8DEFINITION␈αOF␈αPROGRAMMING␈αLANGUAGES.␈α IBM␈αLab,␈αVienna,␈αTR␈α25.087␈α(June
␈↓␈↓ α81968).

␈↓[20]␈α∩Hartmanis,␈α∩Juris␈α∪and␈α∩Hopcroft,␈α∩John␈α∩E,␈α∪"An␈α∩Overview␈α∩of␈α∩Theory␈α∪of␈α∩Computational
␈↓␈↓ α8Complexity",␈αJACM,␈αVol.␈α18,␈α1971,␈αp.␈α444-475.

␈↓[21]␈α→Scott,␈α→D.,␈α→and␈α→Strachey,␈α→C.,␈α→"Towards␈α→a␈α→Mathematical␈α→Semantics␈α→for␈α_Computer
␈↓␈↓ α8Languages",␈α∀in␈α∀PROC.␈α∀SYMP.␈α∀ON␈α∀COMPUTERS␈α∀AND␈α∀AUTOMATA,␈α∀Polytechnic
␈↓␈↓ α8Institute␈αof␈αBrooklyn,␈α1972.

␈↓[22]␈α∃Weyhrauch,␈α∃Richard␈α∃and␈α∃Milner,␈α∀Robin,␈α∃"Program␈α∃Semantics␈α∃and␈α∃Correctness␈α∃in␈α∀a
␈↓␈↓ α8Mechanized␈α+Logic",␈α+in␈α+FIRST␈α+USA-JAPAN␈α+COMPUTER␈α+CONFERENCE
␈↓␈↓ α8PROCEEDINGS,␈αAFIPS␈αand␈αIPSJ,␈αl972.

␈↓[23]␈α_Blum,␈α_Manuel,␈α_"A␈α_Machine-Independent␈α_Theory␈α_of␈α_the␈α_Complexity␈α_of␈α_Recursive
␈↓␈↓ α8Functions,␈αJACM,␈αVol␈α14,␈α1967,␈αpp.␈α322-336
␈↓␈↓ ¬∧RECOMMENDED COURSES:

␈↓␈↓ α8Phil.␈α160␈αAB,␈α162

␈↓␈↓ α8CS␈α156;␈αCS␈α256,␈α257,␈α258,␈α259

␈↓␈↓ α8Theory␈αof␈αComputation␈αSeminar

␈↓␈↓ ¬<RELATED COURSES:

␈↓␈↓ α8EE␈α484

␈↓␈↓ α8Math␈α292␈αABC,␈α293␈αABC